1) Field of the Invention
The present invention relates to an address translation apparatus, an address translation method, and a two-layer address translation apparatus that carry out an address translation from a virtual address into a physical address in a computer system of a virtual storage system at a high speed.
2) Description of the Related Art
Conventionally, in a computer of a virtual storage system, there is prepared a list called a page table for carrying out address translation from a virtual address (VA) to a physical address (PA).
The address translation will be explained below with reference to FIG. 10. FIG. 10 shows a computer system of a virtual storage system. In this computer system, a CPU (central processing unit) 10 executes various operation instructions by making an access to a main memory 20.
The main memory 20 stores a page table 30 for translation of the virtual address VA into the physical address PA. The virtual address VA is an address specified in a computer program, while the physical address PA is an address allocated to a physical memory unit in the main memory 20.
The page table 30 is a table which matches a virtual address VA and a physical address PA. The virtual address VA and the physical address PA are expressed in hexadecimal numbers like “aaaa 0000 0000 0000”.
The virtual address VA has a 64-bit structure <63:0> (bit 0 to bit 63), as shown in FIG. 11A. In the virtual address VA <63:0>, VA <12:0> is an offset value having a 13-bit structure (hereinafter to be described as Off-SET <12:0>).
VA <21:13> is a RAM access address having a 9-bit structure (hereinafter to be described as RAM-ACCS-ADRS <8:0>). This RAM-ACCS-ADRS <8:0> represents an address in a TLB (translation look-aside buffer or address translation buffer) 40 and corresponds to RAM-ACCS-ADRS <8:0> shown in FIG. 10. The TLB 40 will be described in detail later.
Referring back to FIG. 11A, VA <63:22> is a tag having a 42-bit structure (hereinafter to be described as TLB-TAG <41:0>; refer to FIG. 12A), and this is used as an index in the TLB 40. This TLB-TAG <41:0> corresponds to TLB-TAG <41:0> in the TLB 40.
On the other hand, the physical address PA in the page table 30 has a 43-bit structure <42:0>, as shown in FIG. 11B. In this physical address PA <42:0>, PA <12:0> is an offset value having a 13-bit structure (hereinafter to be described as Off-SET <12:0>), and this is equivalent to Off-SET <12:0> shown in FIG. 11A. PA <42:13> is data corresponding to the physical address (hereinafter to be described as TLB-DATA <29:0>; refer to FIG. 12B).
If the TLB 40 is not available but the address translation is to be carried out, a not shown instruction processing section of the CPU 10 must make access to the main memory 20 and translates the virtual address VA into the physical address PA with reference to the page table 30.
However, when the CPU 10 makes access to the main memory 20 and refers to the page table 30 for the address translation, a lot of processing time is disadvantageously required. This results in low processing speed.
To overcome the time problem, the TLB 40 is provided in a not shown RAM (random access memory) in the CPU 10. This RAM can be accessed at a high speed.
This TLB 40 has 512 entries, for example. Assume that, in the TLB 40, values are expressed in hexadecimal numbers such as “0000” and “2aaa 8000 0000”. In each entry of the TLB 40, there are stored, TLB-TAG <41:0> (tag) as an index, and TLB-DATA <29:0> (data) corresponding to the physical address, as TLB data respectively.
TLB-TAG <41:0> in the TLB 40 corresponds to TLB-TAG <41:0> in the virtual address VA (refer to FIG. 11A). TLB-DATA <29:0> in the TLB 40 corresponds to TLB-DATA <29:0> in the physical address PA (refer to FIG. 11B).
In the above structure, at the time of carrying out a data access to the main memory 20, the instruction processing section (not shown) of the CPU 10 searches the TLB 40 by using RAM-ACCS-ADRS <8:0> that is included in the virtual address VA corresponding to the instruction code.
Next, the instruction processing section reads TLB-TAG <41:0> (for example, 2aaa 8000 0000) and TLB-DATA <29:0> (for example, 0000 07f8) that are stored in the address shown by RAM-ACCS-ADRS <8.0> from the TLB 40.
Next, the instruction processing section compares the above TLB-TAG <41:0> (for example, 2aaa 8000 0000) with TLB-TAG <41:0> included in the virtual address VA.
Assume that both TLB-TAG <41:0> coincide with each other. The instruction processing section reads the corresponding TLB-DATA <29:0> (in this case, 0000 07f8) from the TLB 40 as HIT (TLB hit). Then, the instruction processing section combines this TLB-DATA <29:0> with Off-SET <12:0> included in the virtual address VA, and generates a physical address PA, as shown in FIG. 11B.
The instruction processing section carries out a data access to the main memory 20 based on the physical address PA.
Moreover, when it stores execution result data in a main memory 20 after an instruction is executed by the instruction processing section based on an instruction code. TLB 40 mentioned above is referred to and address translation processing for changing the virtual address VA into a physical address PA is performed.
When TLB-TAG <41:0> of the TLB 40 and TLB-TAG <41:0> included in the virtual address VA do not coincide with each other (MISS (TLB miss)), the page table 30 is referred to, and the virtual address VA is translated into the physical address PA.
When a TLB miss has occurred, TLB data that includes TLB-TAG <41:0> included in the virtual address VA and TLB-DATA <29:0> included in the physical address PA, as a pair, are stored into the TLB 40. TLB data is stored in the address shown by RAM-ACCS-ADRS <8:0> that is included in the virtual address VA.
Based on this, from the next time, the TLB 40 is used to translate the virtual address VA into the physical address PA.
There are two kinds of virtual addresses VA. They are an instruction virtual address, and an operand virtual address. The instruction virtual address corresponds to a physical address at which an instruction code is stored. Therefore, the virtual address VA from which the instruction processing section reads the instruction code by making access to the main memory 20 is the instruction virtual address. Hereinafter, the access relating to the instruction virtual address will be called an instruction access.
On the other hand, the operand virtual address corresponds to the physical address from/into which data of a result of the execution of an instruction is read/stored in the main memory 20, when the instruction is executed based on the instruction code. Therefore, the virtual address VA at which the instruction processing section stores data of the execution result by making access to the main memory 20 is the operand virtual address. Hereinafter, the access relating to the operand virtual address will be called an operand access.
Similarly, there are two kinds of TLB data stored in the TLB 40. They are operand TLB data, and instruction TLB data. The operand TLB data corresponds to the operand virtual address. On the other hand, the instruction TLB data corresponds to the instruction virtual address.
Referring to FIG. 10, the operand TLB data and the instruction TLB data coexist in one TLB 40. When there is an operand access to the page table 30 due to a TLB miss, the operand TLB data is stored into the TLB 40.
Similarly, when there is an instruction access to the page table 30 due to a TLB miss, the instruction TLB data is stored into the TLB 40.
However, the TLB data of the same RAM-ACCS-ADRS <8:0> is stored into the same address. Therefore, the TLB data that is stored this time is overwritten onto the TLB data stored in the past, regardless of the instruction TLB data and the operand TLB data.
Conventionally, in the pipeline control, an access collision has occurred that an operand access and an instruction access are generated at the same time.
In this case, one of the accesses becomes valid, and the other access is abandoned. For example, when the operand access is valid, the address translation that uses the TLB 40 is executed corresponding to the operand access. On the other hand, the instruction access is retried by the instruction processing section, after a time out due to the abandon. Therefore, there is a problem that the processing speed of the address translation is lowered because of the time loss following the time out.
Further, conventionally, the operand TLB data and the instruction TLB data have been stored indiscriminately in a mixed state in the TLB 40. Therefore, when a TLB miss of the operand access occurs continuously and when overwriting of the entry occurs continuously, the proportion of the operand TLB data in the TLB 40 increases.
On the other hand, the proportion of the instruction TLB data in the TLB 40 decreases, and a TLB hit rate is lowered. In this instance, as the number of access to the page table 30 increases, the processing speed is lowered as a result.